package net.tp.algo.text.sa;

import net.tp.algo.text.SuffixTree;
import static net.tp.util.Utils.*;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author Trung Phan
 *
 */
public class ST2SA {


    /**
     *
     * <p>Build suffix array from suffix tree</p>
     *
     * @param st suffix tree root node
     * @return suffix array
     */
    public static int[] buildSA(SuffixTree.Node st) {

        List<Integer> sa = new ArrayList<>();

        dfsInLexicalOrder(st, sa);

        return toIntArray(sa);
    }

    private static void dfsInLexicalOrder(SuffixTree.Node st, List<Integer> sa) {
        if (st.isLeaf()) {
            sa.add(st.getText().length() - st.getStringDepth());
        }
        else {
            for (Character c : st.edges()) {
                SuffixTree.Edge e = st.edge(c);
                dfsInLexicalOrder(e.getNextNode(), sa);
            }
        }

    }


}
